#include <stdio.h>
#include "heap.h"

void heap_init(heap_t *h) 
{
	h->node_cnt = 0;
}

void heap_print(heap_t *h)
{
	int i;

	printf("heap_print:");
	for (i = 0; i < h->node_cnt; i++)
		printf("%d ", h->array[i]);
	printf("\n");
}

void siftup(heap_t *h, int sif_pos) 
{
	int tmp, pare_pos;

	while(sif_pos > 0) {
		pare_pos = sif_pos >> 1;
		if (h->array[sif_pos] > h->array[pare_pos])
			break;
		tmp = h->array[sif_pos];
		h->array[sif_pos] = h->array[pare_pos];
		h->array[pare_pos] = tmp;
		sif_pos = pare_pos;
	}
}

int heap_insert(heap_t *h, int new)
{
	int ins_pos, ret = 0;

	ins_pos = h->node_cnt;
	if (ins_pos >= HEAP_SIZE)
		ret = -1;
	else {
		h->array[ins_pos] = new;
		siftup(h, ins_pos);
		h->node_cnt ++;
	}
	return ret;
}

void siftdown(heap_t *h)
{
	int left_c, swap_c, pos = 0, tmp;
	int *array = h->array;

	left_c = 1;
	do {
		if (left_c >= h->node_cnt)
			break;
		if (left_c + 1 < h->node_cnt) {
			if (array[left_c] > array[left_c + 1])
				swap_c = left_c + 1;
			else 
				swap_c = left_c;
		}
		if (array[pos] > array[swap_c]) {
			tmp = array[pos];
			array[pos] = h->array[swap_c];
			array[swap_c] = tmp;
			pos = swap_c;
			left_c = (pos << 1) - 1;
			continue;
		}
		break;
	} while (1);
}

int heap_exact(heap_t *h)
{
	int ret = -1;

	if (h->node_cnt != 0) {
		ret = h->array[0];
		h->node_cnt--;
		if (h->node_cnt >= 1) {
			h->array[0] = h->array[h->node_cnt];
			siftdown(h);
		}
	}
	
	return ret;
}

void heap_exact_all(heap_t *h) 
{
	int value;

	while (h->node_cnt) {
		value = heap_exact(h);
		printf("%d ", value);
	}
	printf("\n");	
}


